package cn.edu.ncepu;

import java.util.ArrayList;
import java.util.List;

/**
 * 拉格朗日插值构建工具
 */
public class LagrangeInterpolation {

    /**
     * 生成拉格朗日分式项
     * @param data 插值节点 [[x0,y0], [x1,y1], ...]
     * @param j 当前项索引
     * @return 拉格朗日分式
     */
    private static LagrangeFraction createFraction(List<List<Double>> data, int j) {
        List<Double> numerators = new ArrayList<>();
        double denominator = 1.0;
        double xj = data.get(j).get(0);

        for (int i = 0; i < data.size(); i++) {
            if (i != j) {
                double xi = data.get(i).get(0);
                numerators.add(xi);
                denominator *= (xj - xi);
            }
        }

        return new LagrangeFraction(numerators, denominator);
    }

    /**
     * 构建拉格朗日插值多项式
     * @param data 插值节点 [[x0,y0], [x1,y1], ...]
     * @return 化简后的拉格朗日多项式
     */
    public static LagrangePolynomial interpolate(List<List<Double>> data) {
        List<LagrangeItem> items = new ArrayList<>();
        for (int i = 0; i < data.size(); i++) {
            List<Double> point = data.get(i);
            double y = point.get(1);
            LagrangeFraction fraction = createFraction(data, i);
            items.add(new LagrangeItem(y, fraction));
        }
        return new LagrangePolynomial(items);
    }

    // 测试方法
    public static void main(String[] args) {
        // 测试数据：[[0,1],[2,5],[4,17]] → 对应多项式 x² + 1
        List<List<Double>> data = new ArrayList<>();
        data.add(List.of(0.0, 1.0));
        data.add(List.of(2.0, 5.0));
        data.add(List.of(4.0, 17.0));

        LagrangePolynomial polynomial = LagrangeInterpolation.interpolate(data);

        // 输出测试结果
        System.out.printf("%.1f %.1f %.1f%n",
                polynomial.apply(0.0),
                polynomial.apply(2.0),
                polynomial.apply(4.0));

        System.out.printf("%.1f %.1f %.1f%n",
                polynomial.apply(1.0),
                polynomial.apply(3.0),
                polynomial.apply(5.0));

        // 输出原始拉格朗日表达式
        System.out.println("原始拉格朗日表达式：");
        System.out.println(polynomial);

        // 输出化简后的多项式系数（霍纳形式）
        System.out.println("化简后的多项式系数（最高次到常数项）：");
        System.out.println(polynomial.getPolynomial());
    }
}